#include <bits/stdc++.h>
using namespace std;

/*
head 为null 时 单链表L为空         
head->next 为 null 时， 单链表L为空
优点  链表的第一个位置 和其他位置的操作统一空表和非空表的操作统一
  */
// 指针结构体
typedef struct LNode{
    int data;
    struct LNode *next;
}LNode, *LinkList;

// 单链表的基本操作
/*
1. 头插法建立单链表
    s->next = L.next;
    L.next = s;
2. 尾插发建立单链表
    r->next = s;
    r = s;
3. 按序号查找节点值
4. 按值查找节点值
5. 删除
6. 插入
    p = GetElem(L,i-1);
    s->next = p -> next;
    p->next = s;
7. 求表长
*/
// 头插法
LinkList List_HeadInsert(LinkList &L){
    // 待插入的节点
    LNode *s; int x;
    // 初始化头结点
    L = (LinkList)malloc(sizeof(LNode));
    L->next = NULL;
    
    scanf("%d", &x);
    while(x != 9999){
        s = (LNode*)malloc(sizeof(LNode));
        s->data = x;
        // 头插
        s->next = L->next;
        L->next - s;
        scanf("%d", &x);
    }
    return L;
}

// 尾插法
 LinkList List_TailInsert(LinkList &L){
    int x;
    // 初始化头结点
    L = (LinkList)malloc(sizeof(LNode));
    LNode *s, *r = L;
    scanf("%d", &x);
    while(x!=9999){
        // 初始化一个新的节点
        s = (LNode*)malloc(sizeof(LNode));
        s->data = x;
        // 尾插
        r->next = s;
        r = s;
        scanf("%d", &x);
    }
    r->next = NULL;
    return L;
}

// 按序号查找 返回类型是指针型变量
LNode *GetElem(LinkList L, int i){
    int j = 1;
    LNode *p = L->next;
    if(i == 0) return L; // 返回头结点
    if(i < 1) return NULL; // 查找失败
    while(p && j < i){
        p = p -> next;
        j++;
    }
    return p;
}

LNode *LocateElem(LinkList L, int e){
    LNode *p = L->next;
    while(p!=NULL && p->data!=e){
        p = p->next;
    }
    return p;
}


/* 获取元素的前驱结点 */
LinkList FindPrevNode(LinkList List, int val)
{
    LinkList prev_position = List;

    while (prev_position->next != NULL && prev_position->next->key != val) {
        prev_position = prev_position->next;
    }

    return prev_position;
}

/* 删除一个元素 */
void DeleteElement(LinkList List,int val)
{
    LinkList tmpNode;
    LinkList prev_position = FindPrevNode(List, val);
    if (prev_position->next == NULL) {
        printf("要删除的元素不存在！\n");
    }
    else {
        tmpNode = prev_position->next;
        prev_position->next = tmpNode->next;
        free(tmpNode);
    }

}



int main(){
    LinkList L;
    L = List_HeadInsert(L);
    return 0;
}